package j2025.j02;

/**
 * @Author 猫大仙
 */
public class j0203 {
 /**
  * 97. 交错字符串
  * 给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
  *
  * 两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空
  * 子字符串
  * ：
  *
  * s = s1 + s2 + ... + sn
  * t = t1 + t2 + ... + tm
  * |n - m| <= 1
  * 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
  * 注意：a + b 意味着字符串 a 和 b 连接。
  * @param s1
  * @param s2
  * @param s3
  * @return
  */
 public boolean isInterleave(String s1, String s2, String s3) {
  int m = s1.length();
  int n = s2.length();
  if(m+n!=s3.length()){
   return false;
  }
  s1 = " "+s1;s2 = " "+s2;s3 = " "+s3;
  boolean[][] dp = new boolean[m+1][n+1];
  dp[0][0] = true;
  for (int i = 1; i <= n; i++) {
   if(s2.charAt(i)==s3.charAt(i))dp[0][i] =true;
   else break;
  }
  for (int i = 1; i <= m; i++) {
   if(s1.charAt(i)==s3.charAt(i))dp[i][0] =true;
   else break;
  }
  for (int i = 1; i <= m; i++) {
   for (int j = 1; j <= n; j++) {
    dp[i][j] = (s1.charAt(i)==s3.charAt(i+j) && dp[i-1][j])||(s2.charAt(j)==s3.charAt(i+j) && dp[i][j-1]);
   }
  }
  return dp[m][n];
 }
}
